

public class Test47_1 {
    public static int getMaxValue(int[][] values,int  rows,int cols){
        if (values == null || rows <= 0 || cols <= 0) return  0;
        int[][] dp = new int[rows][cols];

        //动态规划法
        for (int i = 0;i<rows;i++){
            for (int j = 0; j <cols;j++){
                if (i == 0 && j == 0) dp[i][i] = values[i][j];
                else  if (i == 0  && j > 0) dp[i][j] = dp[i][j-1] + values[i][j];
                else if (i > 0  && j == 0) dp[i][j] = dp[i-1][j] + values[i][j];
                else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) + values[i][j];
            }
        }
        return dp[rows-1][cols-1];

    }

    public static int getMaxValue2(int[][] values,int  rows,int cols){
        if (values == null || rows <= 0 || cols <= 0) return  0;
        //滚动数组
        int[] dp = new int[cols + 1];
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                dp[j] = Math.max(dp[j], dp[j - 1]) + values[i - 1][j - 1];
            }
        }

        return dp[cols];

    }
    public static void main(String[] args) {
        int[][] data = {
                {1,10,3,8},
                {12,2,9,6},
                {5,7,4,11},
                {3,7,16,5}};
        System.out.println(getMaxValue(data,4,4));
        System.out.println(getMaxValue2(data,4,4));
    }
}
